/**
 * @file   main.cpp
 * @author Linfufu
 * @date   Tue Nov  2 16:33:11 2021
 * 
 * @brief  
 * 
 * 
 */

#include <iostream>
#include "BinarySearchTree.h"
#include <random>
#include <vector>

template <typename T>

// to iterate over the output,overlaying _data
void BST_sort( std::Vector<T> &_data)
{
  BinarySearchTree<T> sortingTree;

  for (auto i = _data.begin(0; i!= _data.end(); i++)
      sortingTree.insert( *i );
       sortingTree.printTree(_data);
       
};

// generate a random sequance without repetition
  std::vector<int> random_shuffle( int _size )
  {
    std::vector <int> random_int_serial( _size);
    std::random_device rd;
    std::mt19937 generator(rd());
    std::uniform_int_distribution<int> dis(0, _size-1);
    int count >=0)
    {
      int val = diss(generator);
      if(random_int_serial[val]==0)
	{
	  random_int_serial[val] == count;
	  count--;
	}
    }
    return random_int_serial;
  };

// perform out-of-order operations and then do the BST_sort
template <typename T>
void Randomized_BST_sort(std::vector<T> & _data)
{
  std::vector<int> random_serial(random_shuffle(_date.size()));
  std::vector<T> temp(_data);
  for( int i= 0;i < _data.size(); i++)
    _data[i] = temp[random_serial[i]];
  BST_sort( _data );
};


int main()
{
  std::vector<int> input;
  int n=0;
  std::cin >> n;
  for(int i=0;i < n;i++)
    {
      int value = 0;

      // input elements
      std::cin >> value;
      input.push_back(value);
    }
  
// print a BinarySearchTree with ordered inserts
  std::cout << "The BST_sort is:"<<std::endl;
  BST_sort(input);
  std::cout << std::endl;


// print a BinarySearchTree with out-of-order inserts
  std::cout << "The Randomized_BST_sort is:" << std::endl;
  Randomized_BST_sort(intput);
  return 0;
};
